Corelab Seminar
2010-2011
Constantinos Daskalakis (MIT)
Fixed-Point Theorems, Nash Equilibria, and Harnessing Uncertainty
Abstract.
Recent results have shown that computing Nash equilibria is an
intractable problem. It is not NP-hard, since Nash's theorem shows that a Nash equilibrium exists in every game, and this makes it unlikely that
the problem is NP-hard. Instead, it is as intractable as any fixed-point computation problem in a precise technical sense. In the first part of
the talk, we survey results on the complexity of the Nash equilibrium. In view of these results, the credibility of the Nash equilibrium is
questioned: how do markets and players converge to equilibria, if finding them is an intractable problem? In the second part of the talk,
we discuss ways to go around the computational barrier, such as looking at approximation or special cases of the problem. A particularly
promising direction is to develop probabilistic tools to exploit algorithmically the uncertainty and symmetry that is inherent in certain game-theoretic settings. We present recent results in approximating equilibria of anonymous games, and optimally solving multi-dimensional pricing problems.